/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <cstddef> // for NULL

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    // 思路： 使用两个指针分别遍历两个链表，当一个指针到达链表末尾时，将其重定向到另一个链表的头部。这样两个指针在第二次遍历时会同时到达交点（如果存在交点），否则会同时到达链表末尾（NULL）。
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *h1 = headA;
        ListNode *h2 = headB;
        while (h1 != h2)
        {
            if (!h1)
            {
                h1 = headB;
            }
            else
            {
                h1 = h1->next;
            }
            if (!h2)
            {
                h2 = headA;
            }
            else
            {
                h2 = h2->next;
            }
        }
        return h1;
    }
};